import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class SlidingWindow {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> ret = new ArrayList<>();
        int size = words.length;//words中字符串个数
        int strLen = words[0].length();//每个字符串的长度
        Map<String, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < size; i++) {//将words中的字符串信息存入hashMap中
            hashMap.put(words[i], hashMap.getOrDefault(words[i], 0) + 1);
        }
        int sLen = s.length();
        int n = 0;
        while (n < strLen) {//循环size次
            Map<String, Integer> hashMap1 = new HashMap<>();
            for (int left = n, right = n, count = 0; right < sLen - strLen + 1; right += strLen) {//count为有效字符串个数
                String subString = s.substring(right, right + strLen);
                hashMap1.put(subString, hashMap1.getOrDefault(subString, 0) + 1);
                if (hashMap1.get(subString) <= hashMap.getOrDefault(subString, 0)) {
                    count++;
                }
                if (right - left >= size * strLen) {
                    String subString1 = s.substring(left, left + strLen);
                    if (hashMap1.get(subString1) <= hashMap.getOrDefault(subString1, 0)) {
                        count--;
                    }
                    hashMap1.put(subString1, hashMap1.get(subString1) - 1);
                    left += strLen;
                }
                if (count == size) {
                    ret.add(left);
                }
            }
            n++;
        }
        return ret;
    }
}
